Now that we understand the comparison and shifting mechanism required to insert the key into the sorted prefix, let's trace the full execution of Insertion Sort using our standard input array, $A = [8, 2, 5, 1, 6]$.

  • The core adaptability of Insertion Sort comes from its inner while loop, which executes only as many times as necessary to find the correct insertion point. This makes it highly efficient for arrays that are already nearly sorted.
  • In the visualization below, note how elements in the sorted prefix ($A[0..i-1]$) are shifted to the right (A[j+1] = A[j]) until an element smaller than the key is found, or the beginning of the array is reached (j < 0).
  • The sorted prefix (shaded in #94a3b8) grows by one element in each iteration of the outer loop $i$.
Python Implementation: insertion_sort
1def insertion_sort(A):
2    n = len(A)
3    # Outer loop: iterate through the array to grow the sorted prefix
4    for i in range(1, n):
5        # 1. Store the current element (the 'key')
6        key = A[i]
7        j = i - 1
8        # 2. Inner loop: Shift elements in the sorted prefix (> key)
9        while j >= 0 and A[j] > key:
10            A[j + 1] = A[j]
11            j -= 1
12        # 3. Insert the key into its correct position
13        A[j + 1] = key
14    return A